#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

// 定义内核风格的双向循环链表头
struct list_head {
    struct list_head *next, *prev;
};

// 初始化链表头宏
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

// 初始化链表节点
static inline void INIT_LIST_HEAD(struct list_head *head) {
    head->next = head;
    head->prev = head;
}

// 向链表头部添加节点（栈顶操作）
static inline void list_add(struct list_head *new_node, struct list_head *head) {
    new_node->next = head->next;
    new_node->prev = head;
    head->next->prev = new_node;
    head->next = new_node;
}

// 从链表中删除节点
static inline void list_del(struct list_head *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 容器_of宏：通过链表节点获取结构体指针
//#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__m = (ptr); \
    (type *)( (char *)__m - offsetof(type, member) ); \
})

// 栈元素结构体（包含数据和链表节点）
struct stack_node {
    int data;          // 数据域
    struct list_head list; // 链表节点
};

// 栈结构体（包含链表头和大小）
struct stack {
    struct list_head head; // 链表头（虚拟节点，不存储数据）
    int size;              // 栈大小
};

// 初始化栈
void stack_init(struct stack *stack) {
    INIT_LIST_HEAD(&stack->head); // 初始化双向循环链表
    stack->size = 0;
}

// 判断栈是否为空
int stack_is_empty(struct stack *stack) {
    return (stack->head.next == &stack->head); // 头节点的next指向自身表示空
}

// 压栈（向栈顶添加元素）
void stack_push(struct stack *stack, int data) {
    struct stack_node *new_node = malloc(sizeof(struct stack_node));
    if (!new_node) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->data = data;
    list_add(&new_node->list, &stack->head); // 插入到链表头部（栈顶）
    stack->size++;
}

// 弹栈（从栈顶删除元素并返回数据）
int stack_pop(struct stack *stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "Error: stack is empty\n");
        exit(EXIT_FAILURE);
    }
    struct list_head *top = stack->head.next; // 栈顶节点（头节点的下一个节点）
    struct stack_node *node = container_of(top, struct stack_node, list);
    int data = node->data;
    
    list_del(top); // 删除节点
    free(node);
    stack->size--;
    return data;
}

// 查看栈顶元素（不删除）
int stack_peek(struct stack *stack) {
    if (stack_is_empty(stack)) {
        fprintf(stderr, "Error: stack is empty\n");
        exit(EXIT_FAILURE);
    }
    struct list_head *top = stack->head.next;
    struct stack_node *node = container_of(top, struct stack_node, list);
    return node->data;
}

// 获取栈大小
int stack_size(struct stack *stack) {
    return stack->size;
}

// 示例用法
int main() {
    struct stack stack;
    stack_init(&stack);

    // 压栈操作
    stack_push(&stack, 10);
    stack_push(&stack, 20);
    stack_push(&stack, 30);
    printf("Stack size: %d\n", stack_size(&stack)); // 输出：3
    printf("Top element: %d\n", stack_peek(&stack)); // 输出：30

    // 弹栈操作
    printf("Pop: %d\n", stack_pop(&stack)); // 输出：30
    printf("New top: %d\n", stack_peek(&stack)); // 输出：20
    printf("Stack size: %d\n", stack_size(&stack)); // 输出：2

    return 0;
}
